{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 集合与字典的性能"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run this cell first!\n",
    "\n",
    "import time\n",
    "import random\n",
    "from matplotlib import pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 感受 *缓慢*\n",
    "\n",
    "在之前的 notebook 中，你*看到了*列表运行的速度是多么的缓慢。但随着列表变得越来越大，执行归属测试所需的时间也会变得越来越长。\n",
    "\n",
    "但你还是可以*感受*到速度的缓慢。比较一下，运行下面两个单元格各自需要多长时间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Execution complete! That took 0.9230000000000071 milliseconds\n"
     ]
    }
   ],
   "source": [
    "# SMALL list membership tests\n",
    "\n",
    "small_list = list(range(10)) # ten element list of integers\n",
    "nonexistent_element = -1\n",
    "num_trials = 5000\n",
    "\n",
    "start = time.clock()\n",
    "\n",
    "# do lots of membership tests\n",
    "for _ in range(num_trials):\n",
    "    nonexistent_element in small_list\n",
    "\n",
    "end = time.clock()\n",
    "millis = (end-start) * 1000\n",
    "print(\"Execution complete! That took\", millis, \"milliseconds\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Execution complete! That took 4822.650000000001 milliseconds\n"
     ]
    }
   ],
   "source": [
    "# BIG list membership tests\n",
    "\n",
    "big_list = list(range(100000)) # 100K element list of integers\n",
    "nonexistent_element = -1\n",
    "num_trials = 5000\n",
    "\n",
    "start = time.clock()\n",
    "\n",
    "# do lots of membership tests\n",
    "for _ in range(num_trials):\n",
    "    nonexistent_element in big_list\n",
    "\n",
    "end = time.clock()\n",
    "millis = (end-start) * 1000\n",
    "print(\"Execution complete! That took\", millis, \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "那太**无聊** 了，对吧？\n",
    "\n",
    "等待代码执行，即使只需要几秒钟，也已被证明是世界上最枯燥的事情。当无人驾驶汽车的代码运行速度很慢时，它可能会非常危险。\n",
    "\n",
    "幸运的是，我们通常可以通过选择正确的数据结构来**大大**加快代码的运行速度。\n",
    "\n",
    "### 感受 *速度*\n",
    "\n",
    "下面的代码单元格与上面的代码单元格完全相同，除了它们在第一行中使用`set`而不是`list` 。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Execution complete! That took 0.7719999999995508 milliseconds\n"
     ]
    }
   ],
   "source": [
    "# SMALL set membership tests\n",
    "\n",
    "small_set = set(range(10)) # ten element list of integers\n",
    "nonexistent_element = -1\n",
    "num_trials = 5000\n",
    "\n",
    "start = time.clock()\n",
    "\n",
    "# do lots of membership tests\n",
    "for _ in range(num_trials):\n",
    "    nonexistent_element in small_set\n",
    "\n",
    "end = time.clock()\n",
    "millis = (end-start) * 1000\n",
    "print(\"Execution complete! That took\", millis, \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 拭目以待吧！\n",
    "\n",
    "![drum roll](https://d17h27t6h515a5.cloudfront.net/topher/2017/November/5a04cbf1_drum-roll/drum-roll.gif)\n",
    "\n",
    "还记得大列表的运行速度*慢得多么让人崩溃*吗？现在，抓紧你的座位，拭目以待吧！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Execution complete! That took 0.8119999999998129 milliseconds\n"
     ]
    }
   ],
   "source": [
    "# BIG set membership tests\n",
    "\n",
    "big_set = set(range(100000)) # 100K element list of integers\n",
    "nonexistent_element = -1\n",
    "num_trials = 5000\n",
    "\n",
    "start = time.clock()\n",
    "\n",
    "# do lots of membership tests\n",
    "for _ in range(num_trials):\n",
    "    nonexistent_element in big_set\n",
    "\n",
    "end = time.clock()\n",
    "millis = (end-start) * 1000\n",
    "print(\"Execution complete! That took\", millis, \"milliseconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![fast car](https://d17h27t6h515a5.cloudfront.net/topher/2017/November/5a04cd26_fast-sport-car-1466168667pxr/fast-sport-car-1466168667pxr.jpg)\n",
    "\n",
    "### 退后一步\n",
    "\n",
    "\"对不起，你要重复运行代码。有时候我在编程时会太过激动，以至于忽略了那些声音“把你的动作连贯起来！写一个函数，不要再重复了！”\n",
    "\n",
    "现在我要听听那个声音，清理这个代码，并告诉你集合运行的速度有多快。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_data_structure_speed(data_structure_type, size, N=50):\n",
    "    if data_structure_type != dict:\n",
    "        data_structure = data_structure_type(range(size))\n",
    "    else:\n",
    "        data_structure = {num: \"value\" for num in range(size)}\n",
    "    nonexistent_element = -1\n",
    "    \n",
    "    start = time.clock()\n",
    "    for _ in range(N):\n",
    "        nonexistent_element in data_structure\n",
    "    end = time.clock()\n",
    "    \n",
    "    millis = (end-start) * 1000\n",
    "    return millis    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.2300000000001745"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# set test\n",
    "test_data_structure_speed(set, 100000, N=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1058.1040000000003"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# list test\n",
    "test_data_structure_speed(list, 100000, N=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.11699999999947863"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# dictionary test\n",
    "test_data_structure_speed(dict, 100000, N=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZQAAAEWCAYAAABBvWFzAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xu81FX97/HXm0sC4g9RkFCEraalCFKSVlbiJSuP/tLSFDEvXYjjLfNX56fiyUuB/jyl/MzK6OKldqlpHW95SlFMTU1QAtRURLaQJKiAIlpcPueP7xoYNrNnz957Zs+ePe/n4zGP/Z31vaz1nZk9n/mu9V1rKSIwMzPrqB7VLoCZmXUPDihmZlYWDihmZlYWDihmZlYWDihmZlYWDihmZlYWDihWFpImSPpjtctRLpIukvTLTsinQVJI6tXC+vMl/bTS5egISfdJOq4K+b4g6cOdna+1zAGli5F0gqRZklZLWirpbkkfrXa5WhMRjRFxWCWOLWmRpH9JGtQsfU76Mm6oRL5dQURMjYgvt3W/9LlZnR5r0+uXe35Ne8sj6bLmAS4iDo6Im9p7zBby+VJeed+WtCHv+asp390i4pFy5msd44DShUg6B5gGTAWGAMOBHwKfqWa5WtPSr+syexEYn5fnKKBvJ+TbYZ30+mwmIj4dEf0joj/QCFyeex4Rkzq7PG0VET/LK//RwMK88g9qbX+rDgeULkLSAOAS4PSI+G1EvBURayPijoj4ZtpmK0nTJL2cHtMkbZXWjZO0RNL/krQsXd0cJelwSc9Jel3S+Xn5XSTpFkk3SXpT0hOS9slbf26qUnhT0tOSjs5bd4qkhyVdKel14KKU9lDeNiFpkqTnJa2Q9ANJSut6SvqepFclvSjpjGLVPskvgJPynp8M3NDsNdxK0nclvSTpFUnXSOrbntcn6VPk9dlR0q2SlqdzOKvAa/tLSW8Ap0jaL115vpHKdkWzvCakcr8qaXKzY/0yLeeqxyam93+ppP8o8poVJeloSXMlrZT0oKS98tb973T8NyQ9I+ljko4CzgFOTlcKf0nbPirpxLQ8SdIMSVel474g6dC8474nfXbelPT/JP1Y7azSk/QPpat3ZVdOjen9Wq3s6nUXSRem13SRpIPy9t1O0g3pGIvTdj3SuvdJekjSqvT+3tBSGayZiPCjCzyATwHrgF5FtrkEeBTYARgM/Bn4dlo3Lu3/LaA38BVgOfArYBtgJPAOsGva/iJgLXBM2v4bZFcBvdP6Y4EdyX50HAe8BQxN605JeZ0J9CK7UjgFeCivrAHcCWxLdqW1HPhUWjcJeBoYBgwE7k3bFzx3YBFwKPAssCfQE1gMjEj7NaTtpgG3A9ulc74DuLTcr096TWanY70L2BVYCHyy2b5HpW37Ao8AX0jr+wMfSssN6Rx+krbbB/gnsGfesX7ZbNtfA1sDo9I5HNrKZ+s64DvN0j4ELAX2Ta/nROC59H7uk85nCKB0fruk/S4DftrsWI8CJ+a9t2vJgn9P4OvAorxtnwCmpNdtHNnn6qetlP9TwIIC6f8APppXrjXAQekcbkrv1zfS8zOBZ/L2vRv4PtAPGAo8CZyc1v0u7af0nhxQ7e+HWnlUvQB+pDcCJgD/aGWbF4DD855/MvfPmv453wZ6pufbpC+f/fO2nw0clZYvAh7NW9cjfcF8rIW85wCfScunAC81W38KWwaUj+Y9vxk4Ny3fB3w1b92hlBZQLgAuTV8w96QviiD7olX6ctotb78PAy+W+/UB9i9w/ucB1+bt+6dm6/8EXAwMapbekMoxLC/tL8DxecdqHlDel7ft5cDPWvncXMeWAeVaYHKztKZ0biPTuR7U/D2htIAyP2/ddqnM2wJ7pPdgq7z1tzQ/XoHylxpQ7shbdyzwGqD0fHAqR1+yHyJvkX48pfWnAnfnfVavJv2A8qP0h6u8uo7XgEGtVPvsSPZPn9OU0jYeIyLWp+W3099X8ta/TfbrOGdxbiEiNgBLcseTdFKqNlgpaSWwNzCo0L5F/CNveU1e3js227+UY0FW7XUCWfBqXg0xmOzX5uy8Mv+/lJ5TrtdnBLBjLp+U1/lkv+hbOqcvkX2h/k3S45KOaLa+pdeqkPxjN/8MlGoEcH6zcxgM7BQRTwHnkl1JLEtVSUOKHayZ5ucC2fnsCCyPiH/mrS/1vS9F8/dyeaQIwab3e2uyc+8DLM879/9m0/v3dbLP0pOpSvDEMpaxW+v0xkJr0SNkVS5Hkf1qK+Rlsn+Gp9Lz4SmtvXbOLaT642HAy5JGkFXBHAI8EhHrJc0huwrI6cgw1UtTXluUo5iIaJL0InA42Rd0vlfJvjRGRsTfO1C2fAVfH7KqsxcjYvdixd3sScTzwPh0nM8Ct0javgPl+ltabu9nYDFwV0R8r9DKiLgeuF7StsDPgO+QVRN29H0fLGmrvKCyM7CyA8dsj8XAamBgXsDZKH1+vihJwIHAHyX9KSJe6uRy1hxfoXQREbGKrE7+B6mxuJ+k3pI+LenytNmvgQskDVZ2C+23gI70ldhX0mfTVdHZZHX3j5L9iguy+nkknUp2hVIuNwNfk7RT+sL6zzbs+yXg4Ih4Kz8xXUH8BLhS0g4A6fif7EA5W3p9/gK8Iek/JfVVdpPB3pI+2NKBJJ0oaXAqZ+4LdH1L27fif6fPx0iyqpr23LI7HThT0lhl+kv693TcvSQdqOyGj7fTI1fWV4Bd0pdtWz1HFggvSJ/tj5NVZ3WqiHiR7H28XNI2knpI2j2vgf84STumYJN7r9Z1djlrkQNKFxIRV5DdRXMB2Zf5YuAM4P+mTb4DzALmAvPIGji/04EsbyNrcF8BfAH4bGR3lj0NfI/squkVssbfhzuQT3M/Af5Idh5PAr8n+4dt9Qs2Il6IiFktrP5PYAHwqLK7q+4F3tuBcrb0+qwHjgTGkDX8vgr8FBhQ5FifAp6StJqseuX4iHinneV6gOw8ZwDfjYg2dyiNiIeBs4Afk31pPkdWnZhrZ/ge2XktJauu+lba9Uay6qDXJf25jXkGcDxZe9gKsmrC35AF6s42nqxd52/A62RBOVfl9WGyqtPVqXwTI6IjNQF1QwWu+KwOSLoIeE9EVL1+WNKngWsiYkS1y9KVKevAmbsTr1v8YpZ0G9nND5dWuyzWcb5CsU6XqokOl9RL0k7AhWS3alo3J2l/Zf1pekg6kuzK7fZql8vKwwHFqkFkt9CuIKvyeoZNVSrWvQ0DHiJrFP8/wBfTXWXWDbjKy8zMysJXKGZmVhY13Q9l0KBB0dDQUO1imJnVlNmzZ78aEYNb37JtajqgNDQ0MGtWS3eQmplZIZKaWt+q7VzlZWZmZeGAYmZmZVGxgCJpZ0n3K5tL4SlJX0vpF0n6exp4cI6kw/P2OU/SAknPdnDIDDMz62SVbENZB/xHRDwhaRuyoQzuSeuujIjv5m+sbHKf48mGzt4RuFfSHnmjw5Zk7dq1LFmyhHfeae+oFtaSPn36MGzYMHr37l3tophZF1SxgBIRS8nGASIi3pT0DLBTkV0+A9yYRiF9UdICYD+y8aRKtmTJErbZZhsaGhpo3/h1VkhE8Nprr7FkyRJ22WWXahfHzLqgTmlDSWMQvR94LCWdkeYZ+LmkgSltJzafG2EJBQKQsulPZ0matXz58i3yeuedd9h+++0dTMpMEttvv72v/KwqGuc10jCtgR4X96BhWgON8xqrXSQroOIBRVJ/4Fbg7Ih4A/gRsBvZSK1LyUY1hc3n2sgpNFfB9IgYGxFjBw8ufBu1g0ll+HW1amic18jEOybStKqJIGha1cTEOyY6qHRBFQ0oknqTBZPGiPgtQES8EhHr8+av2C9tvoTNJ1rKTWZkZnVs8ozJrFm7ZrO0NWvXMHnG5CqVyFpSybu8RDbT2zNpno9c+tC8zY4G5qfl24HjJW0laRdgd7KJjGpO//5bzt56zTXXcMMNzWet3WTmzJn8+c9tml7CrC68tKrwRIktpVv1VPIurwPIJiWal6aPhWxCnfGSxpBVZy0CvgoQEU9Juhl4muwOsdPbeodXVzZp0qSi62fOnEn//v35yEc+0kklMqsNwwcMp2nVlh27hw8YXoXSWDEVu0KJiIciQhExOiLGpMfvI+ILETEqpf97uhsst8+UiNgtIt4bEXdXqmz5Oqux76KLLuK7383ulL7qqqvYa6+9GD16NMcffzyLFi3immuu4corr2TMmDE8+OCDFSmDWS2acsgU+vXut1lav979mHLIlCqVqHPV0g0JNT2WV0flGvty9bO5xj6ACaMmVCzfyy67jBdffJGtttqKlStXsu222zJp0iT69+/PN77xjYrla1aLcv+Lk2dM5qVVLzF8wHCmHDKlTf+jjfMaO7R/tVTrO6q96nrolWo19o0ePZoJEybwy1/+kl696jqmm5VkwqgJLDp7ERsu3MCisxe1OZjU6l1itXZDQl0HlGo19t11112cfvrpzJ49m3333Zd167rF9OBmXVKtfSnnq7UbEuo6oLTUqFfJxr4NGzawePFiDjroIC6//HJWrlzJ6tWr2WabbXjzzTcrlq9Zvaq1L+V81fiO6oi6DiiVauxbs2YNw4YN2/i44oqNd02zfv16TjzxREaNGsX73/9+vv71r7Ptttty5JFH8rvf/c6N8mZlVmtfyvlq7YaEuq7AL0djXyEbNmwouv6hhx7aIm2PPfZg7ty5HcrXzLY05ZApmzVsQ9f+Us5Xqe+oSqnrgALZG9ZV3xwz67ha+1Jurpa+o+o+oJhZ91dLX8q1rK7bUMzMrHwcUMzMrCwcUMzMrCwcUMzMKqiWxuLqKAeUnIULy3q4KVOmMHLkSEaPHs2YMWN47LHHWtz2uuuu4+WXPfWLWXdTy8O+tIcDCsCll8Juu2V/y+CRRx7hzjvv5IknnmDu3Lnce++97Lzzzi1u74Bi1j3V8rAv7eHbhi+9FL7znWw59/e88zp0yKVLlzJo0CC22morAAYNGgTA7NmzOeecc1i9ejWDBg3iuuuu4+GHH2bWrFlMmDCBvn378sgjj9C3b98O5W9mXUMtD/vSHvV9hZILJmvSL4g1a7LnHbxSOeyww1i8eDF77LEHp512Gg888ABr167lzDPP5JZbbmH27Nl88YtfZPLkyRxzzDGMHTuWxsZG5syZ42Bi1o3U8rAv7VG/VyjNg0lOLqhAu69U+vfvz+zZs3nwwQe5//77Oe6447jggguYP38+n/jEJ4BsTK+hQ4e2ciQzq2W1POxLe9RnQFm4EM4/v+X1a9Zk6487DnbdtV1Z9OzZk3HjxjFu3DhGjRrFD37wA0aOHMkjjzzSzkKbWa2p9WFf2qo+q7x23RWmToV+/Qqv79cvW9/OYPLss8/y/PPPb3w+Z84c9txzT5YvX74xoKxdu5annnoKwEPXm3VhHb3ttyOTg9Wa+rxCgU3VWc2rvfr1gwsu6FDD/OrVqznzzDNZuXIlvXr14j3veQ/Tp09n4sSJnHXWWaxatYp169Zx9tlnM3LkSE455RQmTZrkRnmzLqbWpuCtNkVEtcvQbmPHjo1Zs2ZtlvbMM8+w5557ln6Q/LaUMgST7q7Nr69ZDWuY1kDTqqYt0kcMGMGisxd1foHKRNLsiBhb7uPW7xVKTi54nH++g4mZbabebvvtqPpsQ2nuvPPghRccTMxsM/V2229HOaDktLMB3sy6r1qbgrfaHFDMzFowYdQEph85nREDRiDEiAEjmH7kdDfIt8BtKGZmRXi2x9L5CsXMzMrCAaUCevbsyZgxYxg5ciT77LMPV1xxBRs2bABg1qxZnHXWWUX3nzp16mbPP/KRj1SsrGZm5eJ+KBXQv39/Vq9eDcCyZcs44YQTOOCAA7j44ovbvH9nWLduHb16lVb72RVeXzPrmEr1Q/EVCrBqFYwcmf0ttx122IHp06dz9dVXExHMnDmTI444Ash61J966qmMGjWK0aNHc+utt3Luuefy9ttvM2bMGCZMyOpt+/fvD0BE8M1vfpO9996bUaNGcdNNNwEwc+ZMxo0bxzHHHMP73vc+JkyYQO6HwiWXXMIHP/hB9t57byZOnLgxfdy4cZx//vkceOCBTJkyhV122YW1a9cC8MYbb9DQ0LDxuZlZKSoWUCTtLOl+Sc9IekrS11L6dpLukfR8+jswpUvSVZIWSJor6QOVKltzd90FTz8Nv/99ZY6/6667smHDBpYtW7ZZ+re//W0GDBjAvHnzmDt3LgcffDCXXXYZffv2Zc6cOTQ2bj5m0G9/+1vmzJnDX//6V+69916++c1vsnTpUgCefPJJpk2bxtNPP83ChQt5+OGHATjjjDN4/PHHmT9/Pm+//TZ33nnnxuOtXLmSBx54gAsvvJBx48Zx1113AXDjjTfyuc99jt69e1fmBTGzbqmSVyjrgP+IiD2BDwGnS9oLOBeYERG7AzPSc4BPA7unx0TgRxUsGwAnnAD9+8PJJ2fPTzope37CCeXPq1DV4r333svpp5++8fnAgQOLHuOhhx5i/Pjx9OzZkyFDhnDggQfy+OOPA7DffvsxbNgwevTowZgxY1i0aBEA999/P/vvvz+jRo3ivvvu2zggJcBxxx23cfnLX/4y1157LQDXXnstp556arvP1czqU8UCSkQsjYgn0vKbwDPATsBngOvTZtcDR6XlzwA3ROZRYFtJFZ0w5JJLYPhwyP0Q790bRoyAb3+7vPksXLiQnj17ssMOO2yWHhFIKvk4xdq7crNDQnZTwLp163jnnXc47bTTuOWWW5g3bx5f+cpXeOeddzZut/XWW29cPuCAA1i0aBEPPPAA69evZ++99y65XGZm0EltKJIagPcDjwFDImIpZEEHyH3L7gQsztttSUprfqyJkmZJmrV8+fIOles978mCytq1sPXW2d+LL86mly+X5cuXM2nSJM4444wtgsdhhx3G1VdfvfH5ihUrAOjdu3fB9ouPf/zj3HTTTaxfv57ly5fzpz/9if3226/FvHPBY9CgQaxevZpbbrmlaFlPOukkxo8f76sTM2uXigcUSf2BW4GzI+KNYpsWSNviJ3lETI+IsRExdvDgwR0u3803Z8Hk4ouzv7/5TYcPubFRfeTIkRx66KEcdthhXHjhhVtsd8EFF7BixQr23ntv9tlnH+6//34AJk6cyOjRozc2yuccffTRjB49mn322YeDDz6Yyy+/nHe/+90tlmPbbbflK1/5CqNGjeKoo47igx/8YNFyT5gwgRUrVjB+/Ph2nLWZ1buK3jYsqTdwJ/CHiLgipT0LjIuIpalKa2ZEvFfSj9Pyr5tv19Lxy3Hb8OOPZ9VeQ4bAK6/A4sUwtuw309WGW265hdtuu41f/OIXLW7j24bNal/NDV+vrH7nZ8AzuWCS3A6cDFyW/t6Wl36GpBuB/YFVxYJJueT/aB8yJHvUozPPPJO7776b31fqVjcz6/YqOZbXAcAXgHmS5qS088kCyc2SvgS8BByb1v0eOBxYAKwBXJHfib7//e9XuwhmVuMqFlAi4iEKt4sAHFJg+wBOL7Bte/Ju091TVppaHlXBzCqv2/WU79OnD6+99pq//MosInjttdfo06dPtYtiZl1Utxu+ftiwYSxZsoSO3lJsW+rTpw/Dhg2rdjHMrIvqdgGld+/e7LLLLtUuhplZ3el2VV5mZlYdDihmZlYWDihmZlYWDihmZlYWDihm1ika5zXSMK2BHhf3oGFaA43zGlvfyWpKt7vLy8y6nsZ5jUy8YyJr1q4BoGlVExPvmAjAhFETiu1qNcRXKGZWcZNnTN4YTHLWrF3D5BmTq1QiqwQHFDOruJdWvdSmdKtNDihmVnHDBwxvU7rVJgcUMytJRxrVpxwyhX69+22W1q93P6YcMqXcxbQqckAxs1blGtWbVjURxMZG9VKDyoRRE5h+5HRGDBiBECMGjGD6kdPdIN/NVHTGxkorNGOjmZVfw7QGmlY1bZE+YsAIFp29qPMLZB1SqRkbfYViZq1yo7qVwgHFzFrlRnUrhQOKmbXKjepWCgcUM2uVG9WtFG6UNzOrM5VqlC9pLC9JY4CPATsCbwPzgRkRsarcBTIzs9pUtMpL0omSZgMXAwOBJuAN4FBgpqSfSfIk42Zm1uoVyvbAxyPirUIrJY0F9gSWlLtgZmZWW4oGlIj471bWuwHDzMyAEu/yknSppH+T1EvSHyS9IumEShfOzMxqR6m3DX86It4AjgCWASOB/6xYqczMrOaUGlByVWOHA7+OiFeB2r3f2MzMyq7UKYDvljQfWA+cLmkQ8M/KFcvMzGpNSVcoEfFN4GBg34hYS9YX5bOVLJiZmdWWUjs29gDGAg2S8ve5qiKlMjOzmlNqG8ptwCRgJ2Bw3qNFkn4uaVmqKsulXSTp75LmpMfheevOk7RA0rOSPtn2UzEzs2oqtQ2lISJGtfHY1wFXAzc0S78yIr6bnyBpL+B4srvHdgTulbRHRKxvY55mZlYlpV6h/EHSwW05cET8CXi9xM0/A9wYEf+MiBeBBcB+bcnPzMyqq9SA8iBwh6TVkl6XtEJSqcGiuTMkzU1VYgNT2k7A4rxtlqQ0MyujxnmNNExroMfFPWiY1lDynPBmpSg1oFxJNtrwQLK2k0G00obSgh8BuwFjgKXA91K6CmxbsJ+LpImSZkmatXz58nYUwaw+Nc5rZOIdE2la1UQQNK1qYuIdEx1UrGxKDSjPA09GxNqIWJ97tDWziHgl7bsB+AmbqrWWADvnbToMeLmFY0yPiLERMXbw4PbENLP6NHnGZNasXbNZ2pq1a5g8Y3KVSmTdTamN8i8D90n6PXkdGiOiTbcNSxoaEUvT06PJ5lUBuB34laQryBrldwf+0pZjm1lxL616qU3pZm1VakBZkh7/VuqBJf0aGAcMkrQEuBAYlybrCmAR8FWAiHhK0s3A08A64HTf4WVWXsMHDKdpVVPBdLNy8BTAZnUi14aSX+3Vr3c/zw1fhyo1BXBrMzb+SNKeLazrK+kkSePLXSgzK78JoyYw/cjpjBgwAiFGDBjhYGJlVfQKRdK+wGTgvcBcYDnQh6yNYxBZ58UfRMQ7FS9pAb5CMTNru0pdobQ2Y+Ns4LOS/o3sjqyhZAND/ndEPFXuwpiZWe0qqVE+Ta51b4XLYmZmNazUfihm1gW4p7t1ZaXeNmxmVdb8Lq1cT3fADevWJbTpCkXSVpUqiJkV557u1tWVFFAk7SdpHtkQLEjaR9L3K1oyM9uMe7pbV1fqFcpVwBHAawAR8VfgoEoVysy21FKPdvd0t66i1IDSIyKaj9ngoVHMOtGUQ6bQr3e/zdL69e7HlEOmVKlEZpsrNaAslrQfEJJ6SjobeK6C5TKzZtzT3bq6ksbykrQDWbXXoSnpXuCMiHi1gmVrlXvKm5m1XVV6yudExDKyOd/NzMwKKimgSBoOnAE05O8TEZ+tTLHMzKzWlNqGcjvwD7JZFn+Q9zCzNnBPd+vOSu0p/6+IuKKiJTHr5tzT3bq7Uq9Qvi/pAkkflDQ696hoycy6Gfd0t+6u1CuUPYAvA58GNqS0AD5eiUKZdUfu6W7dXakB5fNAQ0T8s5KFMevOPKe7dXelVnnNBbapZEHMujv3dLfurtQrlO2Bv0l6DNh4leLbhs1Kl2t4nzxjMi+teonhA4Yz5ZApbpC3bqPUnvKHFEqPiBllL1EbuKe8mVnbVbunfFUDh5mZdX1F21AkPZD+rpD0et5jhaTXO6eIZl2LOyeaFdbaFUpuzpNBlS6IWS1w50SzlrV2l9csgIhYX+jRCeUz61LcOdGsZa0FFHVKKcxqhDsnmrWstSqvwZLOamllRFxV5vKYdWnunGjWstauUHqStZ8MbuFhVlfcOdGsZa1doSyNiG91SknMaoA7J5q1rLWA4jYUs2YmjJrgAGJWQGtVXoe198CSfi5pmaT5eWnbSbpH0vPp78CULklXSVogaa6kD7Q3XzMzq46iASUilnfg2NcBn2qWdi4wIyJ2B2ak55ANi797ekwEftSBfM3MrApKHW24zSLiT0Dz3vSfAa5Py9cDR+Wl3xCZR4FtJQ2tVNmsvrmnu1lllDracLkMiYilABGxVNIOKX0nYHHedktS2tLmB5A0kewqhuHDfaumtY17uptVTmtjeTUfw6tSY3kVavwvOAxyREyPiLERMXbwYN+5bG3jnu5mldPaFUq5x/B6RdLQdHUyFFiW0pcAO+dtNwx4ucx5m7mnu1kFtdYo33zsrgHAkLxHW90OnJyWTwZuy0s/Kd3t9SFgVa5qzKycWurR7p7uZh1XUqO8pP8h6TmyK4nH0t/7Wtnn18AjwHslLZH0JeAy4BOSngc+kZ4D/B5YCCwAfgKc1o5zMWuVe7qbVU6pjfJTgAOAP0bE+yV9AvhcsR0iYnwLq7aY/TGyaSNPL7EsZu3mnu5mlVNqQFkXEcsl9ZCkiLhHkn/SWU1yT3ezyig1oKyStDXwEHCDpGXAhsoVy8zMak2pHRuPAt4BzgZmAn8HjqhQmczMrAaVGlDOS3d6rY2In0XEFcA5lSyYWTHu7W7W9ZQaUJqPyQXwP8pZELNS5Xq7N61qIoiNvd0dVMyqq7We8l+V9CTZrb9P5D2eB57unCKabc693c26ptYa5W8mGxX4UjaNDAzwZkQsK7yLWWW5t7tZ19RaT/kVEbEgIo4F+pJ1RvwEnv7Xqsi93c26plJ7yp9OdrUyPD1uluTe7FYV7u1u1jWV2g/lq8B+EbEaQNJU4M/ADytVMLOWuLe7WddUakARsDbv+Vo837xVkXu7m3U9RQOKpF4RsQ74BfCopFvTqqPZNPOimZlZq20ofwGIiMvJZklcA7wNTIqI71a4bNaNuWOiWffTWpXXxmqtiHgceLyyxbF64Gl4zbqn1gLKYEktDrGShmAxa5NiHRMdUMxqV2sBpSfQHzfAWxm5Y6JZ99RaQFkaEZd0SkmsbgwfMJymVU0F082sdrXWKO8rEys7d0w0655aCyhbTNdr1lETRk1g+pHTGTFgBEKMGDCC6UdOd/uJWY1TNp17bRo7dmzMmjWr2sUwM6spkmZHxNhyH7fU+VDMzMyKckAxM7OycECxdnFPdzNrrtTBIc02ck93MyvEVyjWZp6C18wKcUCxNnOb7QxjAAANrklEQVRPdzMrxAHF2sxT8JpZIQ4o1mbu6W5mhTigWJu5p7uZFeKe8mZmdaZb9ZSXtEjSPElzJM1KadtJukfS8+nvwGqUrZ64L4mZlVM1q7wOiogxeVHyXGBGROwOzEjPrUJyfUmaVjURxMa+JA4qZtZeXakN5TPA9Wn5euCoKpal23NfEjMrt2oFlAD+KGm2pIkpbUhELAVIf3cotKOkiZJmSZq1fPnyTipu9+O+JGZWbtUKKAdExAeATwOnS/p4qTtGxPSIGBsRYwcPHly5EnZz7ktiZuVWlYASES+nv8uA3wH7Aa9IGgqQ/i6rRtnqhfuSmFm5dXpAkbS1pG1yy8BhwHzgduDktNnJwG2dXbZ64r4kZlZund4PRdKuZFclkI12/KuImCJpe+BmYDjwEnBsRLxe7Fjuh2Jm1naV6ofS6cPXR8RCYJ8C6a/hOezNzGpWV7pt2MzMapgDSg1zT3cz60o8Y2ON8qyJZtbV+AqlRrmnu5l1NQ4oNco93c2sq3FAqVHu6W5mXY0DSpW1t2HdPd3NrKtxQKmijgwh757uZtbVeMbGKmqY1kDTqqYt0kcMGMGisxd1foHMrC50qxkbLeOGdTPrThxQqsgN62bWnTigVJEb1s2sO3FAqSI3rJtZd+JGeTOzOuNGeTMz69IcUMzMrCwcUMzMrCwcUMzMrCwcUMzMrCwcUMzMrCwcUDrI0/CamWU8BXAHeBpeM7NNfIXSAZ6G18xsEweUDvBowWZmmzigdIBHCzYz28QBpQM8WrCZ2SYOKB3g0YLNzDbxaMNmZnXGow2bmVmX5oCSb+HC6uzrvKuzf73m3dH9nXdt7t8JHFByLr0Udtst+9uZ+zrv+iu7Xzfn3dn7d5aI6FIP4FPAs8AC4Nxi2+67775RDk+c9fl4udeA2Iv58XKvAfHEWZ8vfeepU2Nl33fHXsyPlX3fHTF1atsy78j+9Zp3LZfdr5vz7uz9CwBmRSW+vytx0HYXBnoCLwC7Au8C/grs1dL25QgoT5z1+XirN9HI+ICIX3F8vNWb0oLK1KkR/fpttm/061f6G96R/es171ouu183593Z+7egXgLKh4E/5D0/Dzivpe07HFCmTo1j1Rhb82b04l8BEb34V2zNm3GsGou/aVOnxvieNxbcd3zPG1t/wzuyf73mXctl9+vmvDt7/yLqJaAcA/w07/kXgKubbTMRmAXMGj58eLtf0HjhhQiI59kt9uSp6MvqgIi+rI69mB8L2DV7eV54obz7Ou/6K7tfN+fd2fu3ol4CyrEFAsr3W9q+HFcob/VW/IbPpcj/RvTiX/EbPhdv9Varv16iX7+C+5Z0SdqR/es171ouu183593Z+xdRLwGlc6u8ImtDOVo3xQBWxHc5JwawIj6rG0tuQzm2562b7fv5nre0qX603fvXa961XHa/bs67s/dvQb0ElF7AQmCXvEb5kS1tX667vH5x3HmxsNeQCIiFvYbEL487t+R9/3LatfGPvg0REP/o2xCPn/bzNuXdkf3rNe9aLrtfN+fd2fsXUhcBJTtPDgeeS3d7TS62bbkCSkRkER/aF/k7sq/zrr+y+3Vz3p29fzN1E1Da8ihrQIlodwNXh/d13tXZv17z7uj+zrs2989TqYDiwSHNzOqMB4c0M7MuzQHFzMzKwgHFzMzKwgHFzMzKwgHFzMzKwgHFzMzKwgHFzMzKoqb7oUhaDjSV8ZCDgFfLeLxa4fOuP/V67j7vzIiIGFzuTGo6oJSbpFmV6OzT1fm860+9nrvPu7Jc5WVmZmXhgGJmZmXhgLK56dUuQJX4vOtPvZ67z7uC3IZiZmZl4SsUMzMrCwcUMzMrCwcUQNKnJD0raYGkc6tdnlJJ+rmkZZLm56VtJ+keSc+nvwNTuiRdlc5xrqQP5O1zctr+eUkn56XvK2le2ucqSSqWRyee986S7pf0jKSnJH2tjs69j6S/SPprOveLU/oukh5L5bpJ0rtS+lbp+YK0viHvWOel9GclfTIvveD/Q0t5dCZJPSU9KenOYmXqTuctaVH6LM6RNCuldc3PeiVm7aqlB9CTbLrhXdk0j/1e1S5XiWX/OPABYH5e2uXAuWn5XOC/0vLhwN2AgA8Bj6X07YCF6e/AtDwwrfsL8OG0z93Ap4vl0YnnPRT4QFrehmzK6L3q5NwF9E/LvYHH0jndDByf0q8B/mdaPg24Ji0fD9yUlvdKn/WtgF3S/0DPYv8PLeXRyed/DvAr4M5iZepO5w0sAgY1S+uSn/VO/TB0xUd6If+Q9/w84Lxql6sN5W9g84DyLDA0LQ8Fnk3LPwbGN98OGA/8OC/9xyltKPC3vPSN27WURxVfg9uAT9TbuQP9gCeA/cl6Qfdq/pkG/gB8OC33Stup+ec8t11L/w9pn4J5dOL5DgNmAAcDdxYrUzc770VsGVC65GfdVV6wE7A47/mSlFarhkTEUoD0d4eU3tJ5FktfUiC9WB6dLlVlvJ/sl3pdnHuq9pkDLAPuIftlvTIi1hUo78ZzTOtXAdvT9tdk+yJ5dJZpwP8CNqTnxcrUnc47gD9Kmi1pYkrrkp/1Xm04qe5KBdK6473ULZ1nW9O7DEn9gVuBsyPijVT1W3DTAmk1e+4RsR4YI2lb4HfAnoU2S3/beo6FfmRW/TWRdASwLCJmSxqXSy5Spm5x3skBEfGypB2AeyT9rci2Vf2s+woli8g75z0fBrxcpbKUwyuShgKkv8tSekvnWSx9WIH0Ynl0Gkm9yYJJY0T8tpVydatzz4mIlcBMsrrybSXlfiDml3fjOab1A4DXaftr8mqRPDrDAcC/S1oE3EhW7TWtSJm6y3kTES+nv8vIfkDsRxf9rDugwOPA7ulOjneRNeDdXuUydcTtQO4OjpPJ2hdy6Selu0A+BKxKl7F/AA6TNDDdxXEYWR3xUuBNSR9Kd32c1OxYhfLoFKk8PwOeiYgr8lbVw7kPTlcmSOoLHAo8A9wPHFOgXPnlPQa4L7JK8duB49PdULsAu5M1zhb8f0j7tJRHxUXEeRExLCIaUpnui4gJRcrULc5b0taStsktk31G59NVP+ud2bjUVR9kd0Y8R1YXPbna5WlDuX8NLAXWkv3S+BJZne8M4Pn0d7u0rYAfpHOcB4zNO84XgQXpcWpe+tj04X0BuJpNIysUzKMTz/ujZJflc4E56XF4nZz7aODJdO7zgW+l9F3JvhgXAL8BtkrpfdLzBWn9rnnHmpzO71nSnT3F/h9ayqMKn/txbLrLq1ufd8r7r+nxVK5cXfWz7qFXzMysLFzlZWZmZeGAYmZmZeGAYmZmZeGAYmZmZeGAYmZmZeGAYl2WpPVphNWnlI2ue46kop9ZSQ2STmhHXpNTPnNTnvun9LMl9WvvORTI5/xyHavAsftJakwjx86X9FAaTQBJf65UvmY5vm3YuixJqyMi94W4A9kosw9HxIVF9hkHfCMijmhDPh8GrgDGRcQ/JQ0C3hXZcBeLyO7lf7XAfj0jGwalXefUhn16xaaxpIptdx4wOCLOSc/fCyyKiH+2JT+z9vIVitWEyIadmAickXoBN0h6UNIT6fGRtOllwMfSVcbXi2yXbyjwau6LNyJeTcHkLGBH4H5J90MWECRdIukx4MPK5qoYlNaNlTQzLfeXdG26Wpgr6XOSLgP6prI1prLlz2XzDUkXpeWZkqZKegD4Wuohf6ukx9PjgBbO4+95r9mzuXOStDr9vSTlP0fS3yVdm9JPVDbPyhxJP5bUsx1vk9W7avR09cOPUh7A6gJpK4AhZEO390lpuwOz0vI4Ui/q9Lzgds2O2Z+st/1zwA+BA/PWLSJv6HCyHvqfL7SerMfxzLT8X8C0vO0GNj8ntpx64BvARWl5JvDDvHW/Aj6aloeTDTvT/DzGkI239AjwHWD3ll5LsrGt5gL7kg0ueQfQO637IXBStd9/P2rv4dGGrdbkRkftDVwtaQywHtijhe1b3S4iVkvaF/gYcBBwk6RzI+K6AsdbTzYoZWsOJRsPKpfHihL2ae6mZsfbS5tGVP43SdtExJt5ecyRtCvZOE2HAo9L+nBEPJN/0DRmUyNwZWSj955BFlgeT8fvSxUHvbTa5YBiNSN9Wa4n+7K7EHgF2Ies6vadFnb7einbRdYWMhOYKWke2WB41xXY9J3YvN1kHZuqjvvkF5fWhwHP37f5/gBv5S33IJsw6u1iB4yI1cBvgd9K2kA2PtUzzTa7CFgSEdfmlfX6iDivlfKaFeU2FKsJkgaTTb96dUQEWZXN0ojYAHyBbApXgDfJpgXOaWm7/GO/V9LueUljgKYWjtfcIrJf9wCfy0v/I3BGXh65+bjXKht6H7JAt4Ok7SVtBRS7kaD58cYUOI8DtGlu8XeRTXfb1GybI8hmtzwrL3kGcEy68SE3l/iIImUxK8gBxbqyXAP2U8C9ZF+qF6d1PwROlvQoWTVW7tf8XGBdus3460W2y9cfuF7S05Lmkn0RX5TWTQfuzjXKF3Ax8N+SHiS7esr5DjAw3b77V7KqtNzx5kpqjIi1wCVks03eCRSbOOksYGxq4H8amFRgm92AB9IV1pPALLasnvsPshsNcg3wl0TE08AFZLMCziWbBXJokbKYFeTbhs3MrCx8hWJmZmXhgGJmZmXhgGJmZmXhgGJmZmXhgGJmZmXhgGJmZmXhgGJmZmXx/wF+yVCE/QFA3AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sizes = list(range(0, 500000, 25000))\n",
    "list_speeds = [test_data_structure_speed(list, size) for size in sizes]\n",
    "set_speeds  = [test_data_structure_speed(set,  size) for size in sizes]\n",
    "dict_speeds = [test_data_structure_speed(dict, size) for size in sizes]\n",
    "\n",
    "plt.scatter(sizes, list_speeds, c='g', marker=\"o\") #green circle\n",
    "plt.scatter(sizes, set_speeds,  c='r', marker=\"D\") #red diamond\n",
    "plt.scatter(sizes, dict_speeds, c='b', marker=\"*\") #blue star\n",
    "\n",
    "plt.xlabel(\"Data Structure Size\")\n",
    "plt.ylabel(\"Total Time (ms)\")\n",
    "plt.legend([\"List\", \"Set\", \"Dictionary\"])\n",
    "plt.title(\"Comparing Membership Testing Times\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正如你所看到的，集合与字典的性能不依赖于集合/字典的大小，而且归属测试的速度一直 **很快**。速度快就好。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
